package a3_p04_ng_sw;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import org.jgrapht.Graphs;
import org.jgrapht.graph.AbstractGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.WeightedPseudograph;


public class AlgoPrim extends AbstractSearchAlgo{
	
	private AbstractGraph<Knoten, DefaultWeightedEdge> graph;
	private WeightedPseudograph<Knoten, DefaultWeightedEdge> miniGraph;
	private int gewicht =0;
	
	
	public AlgoPrim(AbstractGraph<Knoten, DefaultWeightedEdge> graph){
		this.graph=graph;
		algo();
	}
	
	private void algo(){
		miniGraph= new WeightedPseudograph<Knoten, DefaultWeightedEdge>(DefaultWeightedEdge.class);
		Map<Knoten,Knoten> cameFrom =new HashMap<Knoten,Knoten>();
		List<Knoten> allK= new ArrayList<Knoten>(graph.vertexSet());
		//Radom ersten Knoten w�hlen
		Random generator = new Random();
		int random = generator.nextInt(graph.vertexSet().size());
		
		//Knoten init
		for(Knoten knoten : allK){
			miniGraph.addVertex(knoten);
			knoten.setfskore((double) Integer.MAX_VALUE);
		}
		//erster Knoten
		Knoten first = allK.get(random);
		first.setfskore(0.0);
		
		//Prio heap
		Queue<Knoten> prioQ = new PriorityQueue<Knoten>(allK.size(), new KComparator());
	
		prioQ.addAll(allK);
		while(!prioQ.isEmpty()){
			Knoten lowK = prioQ.poll();
			
			if(!cameFrom.isEmpty()){
				DefaultWeightedEdge kleinsteKante = graph.getEdge(cameFrom.get(lowK), lowK) ;
				gewicht+=graph.getEdgeWeight(kleinsteKante);
                DefaultWeightedEdge dwe = graph.getEdge(cameFrom.get(lowK),lowK);
				miniGraph.addEdge(graph.getEdgeSource(dwe), graph.getEdgeTarget(dwe));
			}
			
			for (Knoten knoten : Graphs.neighborListOf(graph, lowK)) {
				if (prioQ.contains(knoten)) {
					Knoten k = allK.get(allK.indexOf(knoten));
					DefaultWeightedEdge tmpKante = graph.getEdge(knoten, lowK);				
					
					if (k.getfskore() >  graph.getEdgeWeight(tmpKante)) {
						prioQ.remove(k);
						k.setfskore( graph.getEdgeWeight(tmpKante));
						prioQ.offer(k);
						cameFrom.put(k, lowK);
					}

				}
			}
			
		
		}
		//System.err.println("blub"+miniGraph);
	}
	
	
	public WeightedPseudograph<Knoten, DefaultWeightedEdge> getMiniGraph(){
		return miniGraph;
	}
	
	public int getGewicht(){
		return gewicht;
	}
	
	@Override
	public List getTheShortestWay() {
        List tmp = new ArrayList();
        tmp.addAll(miniGraph.edgeSet());
		return tmp;
	}
	
	private class KComparator implements Comparator<Knoten>{
		
		@Override 
		public int compare(Knoten k1, Knoten k2) {

			return k1.getfskore().compareTo(k2.getfskore());
		}
	}

	

}
